#ifndef __REMOVENTHENDFROMEND_H__
#define __REMOVENTHENDFROMEND_H__
#include "ListHeader.h"
/*
* leetcode 19 删除链表倒数第 N 个节点
*/

//使用快慢指针, fast 先移动 n 步, 然后当快指针为 nullptr, 删除 slow
List* RemoveNthFromEnd(List* head, int n) {
	//使用虚拟头节点
	List* dummyHead = new List;
	dummyHead->next = head;

	List* slow = dummyHead;
	List* fast = slow;

	//让 fast 走 n + 1 步, 使 slow 指向被删除元素的前一个元素
	while (fast != nullptr && n >= 0) {
		fast = fast->next;
		n--;
	}

	while (fast != nullptr) {
		fast = fast->next;
		slow = slow->next;
	}

	List* temp = slow->next;
	slow->next = temp->next;

	temp->next = nullptr;
	delete temp;

	List* result = dummyHead->next;
	delete dummyHead;
	return result;
}

#endif // !__REMOVENTHENDFROMEND_H__

